#ifndef COMMON_H
#define COMMON_H
//每次新添加功能都在include guard中添加

#if defined(_WIN64) || defined(_WIN32)
#include <Windows.h>
using PAGEID = size_t;
static int wk = 0;
#else
#include <unistd.h>
#include <sys/mman.h>
using PAGEID = size_t;
static int wk = 0;
#endif

#include <iostream>
#include <ctime>
#include <vector>
#include <assert.h>
#include <thread>
#include "Mutex.h"
#include <unordered_map>
using namespace MutexModule;

static const size_t MAX_BYTES = 256 * 1024;
static const size_t NFREELIST = 208;//一个有208个哈希桶
static const size_t NPAGES = 129;//数组从0开始，中心缓存最多的页数
static const size_t PAGE_SHIFT = 13;//用于计算一次向系统获取几个页

// 直接去堆上按页申请空间
inline static void *SystemAlloc(size_t kpage)
{
#if defined(_WIN64) || defined(_WIN32)
	void *ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	void *ptr = mmap(nullptr, kpage << 13, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
	if (ptr == MAP_FAILED)
		ptr = nullptr;
#endif

	if (ptr == nullptr)
		throw std::bad_alloc();

	return ptr;
}

static void *&ChangeOneToTwoPointer(void *obj)
{
	return *(void **)obj;
}
class FreeList
{
public:
	void Push(void* obj)
	{
		//放在自由链表的头部
		assert(obj);
		*(void**)obj = freeList;
		freeList = obj;
		++size;
	}
	//返回值为void* 返回空闲链表的头部，返回一个可分配的空间
	void* Pop()
	{
		assert(freeList);
		//freeList->A->B->nullptr;
		//实际上是freeList中存储了A的地址，A中存了B的地址，B存的是nullptr，
		//所以虽然这个看起来是一个指针，但实际上是一个没有next指针的链表，这是他叫自由链表的原因
		void* next = freeList;
		freeList = *(void**)next;
		return next;
	}
	bool Empty()
	{
		return freeList == nullptr;
	}
	size_t &GetMaxSize()
	{
		return MaxSize;
	}
	void PushRange(void *start, void *end, size_t n)
	{
		ChangeOneToTwoPointer(end) = freeList;
		freeList = start;
		size += n;
	}
	void PopRange(void*& start, void*& end, size_t n)
	{
		if (n > size)
		{
			// 可以选择抛出异常，也可以直接return
			throw std::runtime_error("PopRange: n > size");
			//start = end = nullptr;
			//return;
		}
		assert(n <= size);
		start = freeList;
		end = start;
		// 下面还要进行一次移动，所以向后移动n-1即可
		for (int i = 0; i < n - 1; i++)
		{
			if (end == nullptr)
			{
				// 链表断裂，抛异常或直接return
				throw std::runtime_error("PopRange: free list broken (end == nullptr)");
			}
			end = ChangeOneToTwoPointer(end);
		}
		if (end == nullptr)
		{
			// 链表断裂，抛异常或直接return
			std::cout << "end==nullptr" << std::endl;
			throw std::runtime_error("PopRange: free list broken (end == nullptr)");
		}
		freeList = ChangeOneToTwoPointer(end);//此时freeList指向的就是pop[start,end]后的地址
		ChangeOneToTwoPointer(end) = nullptr;
		size -= n;
	}
	size_t getSize()
	{
		return size;
	}

private:
	void *freeList = nullptr;
	size_t MaxSize = 1;
	size_t size = 0;//分配出去的对象计数
};

//计算对象大小的对齐映射规则
class SizeClass
{
	static inline size_t RoundUp(size_t ByteSize, size_t alignNum)
	{
		return (ByteSize + alignNum - 1) & ~(alignNum - 1);
	}

	static inline size_t Index(size_t Bytes, size_t align_shift)
	{
		assert(Bytes > 0);
		/*if (Bytes % align_shift == 0)
		{
			return Bytes / align_shift - 1;
		}
		else
		{
			return Bytes / align_shift;
		}*/

		// (1 << align_shift),必须要有，否则下标映射关系不对
		// 只要[1,7]字节的话，最后返回-1了，结果出错，而且后续映射的桶的下标都比预期少了1
		return (Bytes + (1 << align_shift) - 1) >> align_shift - 1;
	}

public:
	// 整体控制在最多10%左右的内碎片浪费
	// [1,128]					8byte对齐	    freelist[0,16)
	// [128+1,1024]				16byte对齐	    freelist[16,72)
	// [1024+1,8*1024]			128byte对齐	    freelist[72,128)
	// [8*1024+1,64*1024]		1024byte对齐     freelist[128,184)
	// [64*1024+1,256*1024]		8*1024byte对齐   freelist[184,208)
	// 空间浪费率怎么计算以[129,1024]这个区间为例，最坏情况下申请129个字节，然后内存对齐到144个字节
	// 这就浪费了15个字节，空间浪费率区间[15/144,15/1024];
	// 除了第一个区间浪费率较高外，其余均可以控制在10%左右
	//返回对齐后的长度
	/*static inline size_t RoundUp(size_t ByteSize, size_t alignNum)
	{
		assert(ByteSize <= 0);

		size_t alignSize = 0;
		if (ByteSize % alignNum != 0)
		{
			alignSize = (ByteSize / alignNum + 1) * alignNum;
		}
		else
		{
			alignSize = ByteSize;
		}
		return alignSize;
	}*/
	// 更高效

	static inline size_t RoundUp(size_t Bytes)
	{
		assert(Bytes > 0 && Bytes <= MAX_BYTES);
		//每个区间都要减去和自己对齐数不相等的区间
		if (Bytes <= 128)
		{
			return RoundUp(Bytes, 8);
		}
		else if (Bytes <= 1024)
		{
			return RoundUp(Bytes, 16);
		}
		else if (Bytes <= 8 * 1024)
		{
			return RoundUp(Bytes, 128);
		}
		else if (Bytes <= 64 * 1024)
		{
			return RoundUp(Bytes, 256);
		}
		else if (Bytes <= 256 * 1024)
		{
			return RoundUp(Bytes, 8 * 1024);
		}
		else
		{
			assert(false);
			return -1;
		}
	}

	static inline size_t Index(size_t Bytes)
	{
		assert(Bytes > 0 && Bytes <= MAX_BYTES);
		//每个区间有几个桶
		static int group[4] = {16, 72, 128, 184};
		if (Bytes <= 128)
		{
			return Index(Bytes, 3);
		}
		else if (Bytes <= 1024)
		{
			return Index(Bytes - 128, 4) + group[0];
		}
		else if (Bytes <= 8 * 1024)
		{
			return Index(Bytes - 1024, 7) + group[1];
		}
		else if (Bytes <= 64 * 1024)
		{
			return Index(Bytes - 8 * 1024, 10) + group[2];
		}
		else if (Bytes <= 256 * 1024)
		{
			return Index(Bytes - 64 * 1024, 13) + group[3];
		}
		else
		{
			assert(false);
			return -1;
		}
	}

	//一次thread cache从中心缓存获取多少个
	static size_t NumMoveSize(size_t size)
	{
		//[2,512]一次批量移动多少个对象的上限值
		//小对象一次批量上限高
		//大对象一次批量上限低
		size_t num = MAX_BYTES / size;
		if (num < 2)
		{
			num = 2;
		}
		else if (num > 512)
		{
			num = 512;
		}
		return num;
	}

	// 计算一次向系统获取几个页
	static size_t NumMovePage(size_t size)
	{
		//对齐size的大小，一次分配几个对象
		size_t num = NumMoveSize(size);
		// 返回实际分配的对象的大小
		size_t npage = num * size;
		// 8k是2^13，规定一页大小是8k，右移是为了计算可以分配几个页
		npage >>= PAGE_SHIFT;
		if (npage == 0)
		{
			npage = 1;
		}
		return npage;
	}
};

// #ifndef SPAN1
// #define SPAN1

//用来管理以页为单位的大块内存
struct Span
{
	PAGEID PageId = 0;//大块内存起始页的页号
	size_t n = 0;//页的数量

	//用一个双向链表来管理
	Span* next = nullptr;
	Span* prev = nullptr;

	size_t UseCount = 0;//代表Span的使用个数，用了就++，还回来就--，

	void* freeLists = nullptr;
	bool _isUse = false;   //某个span是否在被使用
};


class SpanList
{
public:
	SpanList()
	{
		// std::cout << "hello<< " << (wk += 1) << "\n";
		Head = new Span;
		Head->next = Head;
		Head->prev = Head;
	}

	Span *Begin()
	{
		return Head->next;
	}

	Span *End()
	{
		return Head;
	}

	bool Empty()
	{
		return Head->next == Head;
	}

	void PushFront(Span *newspan)
	{
		Insert(Begin(), newspan);
	}

	//指定位置前插入指定newSpan
	void Insert(Span *pos, Span *newSpan)
	{
		assert(pos);
		assert(newSpan);

		Span *prev = pos->prev;
		prev->next = newSpan;
		newSpan->prev = prev;

		newSpan->next = pos;
		pos->prev = newSpan;
	}

	//删除指定位置的值
	void Erase(Span *pos)
	{
		assert(pos);
		assert(pos != Head);

		Span *prev = pos->prev;
		prev->next = pos->next;
		pos->next->prev = prev;
	}

	Span *Pop()
	{
		Span *newspan = Begin();
		Erase(newspan);
		return newspan;
	}

private:
	Span *Head;

public:
	Mutex BucketMutex;
};
// #endif // !SPAN1

#endif
